1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <cstdio>
#include <vector>
#include <cstring>
const int maxP = 1e7;
const int maxn = 205;
const int S = 0;
const int T = 204;
using namespace std;
vector <int> p; bool isp[maxP + 5];
void install(){
isp[1] = 1;
for (int i = 2; i <= maxP; i++){
if (!isp[i]) p.push_back(i);
for (int j = 0; j < p.size() && i * p[j] <= maxP; j++){
isp[i * p[j]] = 1;
if (i % p[j] == 0) break;
}
}
}
struct E{
int to, nxt;
}e[maxn * maxn];
int head[maxn], tot = 1;
void addedge(int u, int v){
e[++tot].to = v, e[tot].nxt = head[u];
head[u] = tot;
}
int mat[maxn]; bool vis[maxn];
bool dfs(int cur){
for (int i = head[cur]; i; i = e[i].nxt){
int v = e[i].to;
if (vis[v]) continue;
vis[v] = 1;
if (mat[v] == -1 || dfs(mat[v])){
mat[v] = cur; mat[cur] = v;
return true;
}
}
return false;
}
int abs(int x){return x < 0 ? -x : x;}
vector <int> x[2]; int n, c[maxP + 5];
int main(){
install();
scanf("%d", &n);
for (int a, i = 1; i <= n; i++){
scanf("%d", &a); c[a]++;
}
for (int i = 1; i <= maxP + 1; i++)
if (c[i] != c[i - 1]) x[i & 1].push_back(i);
for (int i = 0; i < x[0].size(); i++)
for (int j = 0; j < x[1].size(); j++)
if (!isp[abs(x[1][j] - x[0][i])]) addedge(i, j + x[0].size());
int flow = 0;
memset(mat, -1, sizeof mat);
for (int i = 0; i < x[0].size() + x[1].size(); i++){
if (mat[i] == -1){
memset(vis, 0, sizeof vis);
flow += dfs(i);
}
}
printf("%d\n", flow + (x[0].size() - flow) / 2 * 2 + (x[1].size() - flow) / 2 * 2 + (x[0].size() - flow) % 2 * 3);
return 0;
}
|